package com.ljy.my_study.leetcode.丑数II;
/** 
* @author James
* @date 2018年9月18日 
*/
public class TestMain {
//	设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
//
//	符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
//
//	我们可以认为1也是一个丑数
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	如果n = 9， 返回 10
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
//		System.out.println(testMain.nthUglyNumber(12));
//		System.out.println(testMain.isUglyNum(10));
		System.out.println(testMain.nthUglyNumber(1665));
	}
	
//	public int nthUglyNumber(int n) {
//        // write your code here
//		int count=1;
//		int num=1;
//		int uglyCount=1;
//		System.out.print(num+"	");
//		if(n==1) {
//			System.out.println();
//			return num;
//		}
//		while(true) {
//			if(count%2==0||count%3==0||count%5==0) {
//				num=count;
//				uglyCount++;
//				System.out.print(num+"	");
//				if(uglyCount==n) {
//					System.out.println();
//					return num;
//				}
//			}
//			count++;
//		}
//    }
	
	public int nthUglyNumber(int n) {
		// write your code here
		int count=1;
		int num=1;
		int uglyCount=0;
//		System.out.print(num+"	");
//		if(n==1) {
//			System.out.println();
//			return num;
//		}
		while(true) {
//			if(count%2==0||count%3==0||count%5==0) {
			if(isUglyNum(count)) {
				num=count;
				uglyCount++;
				System.out.print(num+"	");
				if(uglyCount==n) {
					System.out.println();
					return num;
				}
			}
			count++;
		}
	}
	
	public boolean isUglyNum(int num) {
		int n=num;
		while(true) {
			if(n==1) {
				return true;
			}
			if(n%2==0) {
				n=n/2;
			}else if(n%3==0) {
				n=n/3;
			}else if(n%5==0) {
				n=n/5;
			}else {
				return false;
			}
		}
	}
	
}
